package dawnland03.data.map.algorithm.neighbours;

import dawnland03.data.map.model.MatrixCell;
import dawnland03.data.map.model.Matrix;

import java.util.*;

/**
 * User: Petru Obreja (obrejap@yahoo.com)
 * Date: Feb 6, 2010
 * Time: 11:18:39 AM
 */
public class FindNeighboursAlgorithm {

    /**
     * Computes the map of neighbours for the origin MatrixCell(xStart, yStart).
     * The distance of 1 corresponds to a neighbour, a distance of 2 correspond to the neighbours' neigbours.
     * If minimumDistance < 0 or maximumDistance<minimumDistance, an empty set is returned.
     * If minimumDistance = 0 and maximumDistance = 0, only the origin node is returned.
     *
     * @param matrix             the matrix
     * @param xStart             the x coordinate for origin
     * @param yStart             the y coordinate for origin
     * @param minimumDistance    the minimum distance between origin and neighbours. Should be pozitive.
     * @param maximumDistance    the maximum distance between origin and neighbours. Should be greater than minimumDistance
     * @param predicate          only neighbours accepted by this predicate will be included in the final result
     * @param numberOfNeighbours maximum number of neighbours in the final result; = null if no limit is required; the result will contain only the closest neighbours
     * @return the map of neigbours; key: the distance; value: the neighbours at that distance
     */
    public Map<Integer, Set<MatrixCell>> findNeighbours(Matrix matrix, int xStart, int yStart, int minimumDistance, int maximumDistance, Predicate predicate, Integer numberOfNeighbours) {
        Map<Integer, Set<MatrixCell>> neighboursMap = new HashMap<Integer, Set<MatrixCell>>();
        if (minimumDistance < 0 || (maximumDistance < minimumDistance)) {
            return neighboursMap;
        }
        int currentDistance = 0;
        Map<Integer, Set<MatrixCell>> openMap = new HashMap<Integer, Set<MatrixCell>>(); //the cells which will be iterated
        Set<MatrixCell> closedSet = new HashSet<MatrixCell>(); // the cells which are excluded from the final result; their distance < minimumDistance
        MatrixCell origin = matrix.getMatrixCell(xStart, yStart);
        openMap.put(currentDistance, new LinkedHashSet<MatrixCell>(Arrays.asList(origin)));
        while (currentDistance <= maximumDistance) {
            Set<MatrixCell> currentOpenSet = openMap.get(currentDistance);
            if (currentOpenSet.size() == 0) {
                currentDistance++;
                continue;
            }
            Iterator<MatrixCell> currentOpenSetIterator = currentOpenSet.iterator();
            MatrixCell currentMatrixCell = currentOpenSetIterator.next();
            currentOpenSetIterator.remove();
            if (currentDistance >= minimumDistance) {
                if (!isMatrixCellBetweenNeighbours(currentMatrixCell, neighboursMap)) {
                    if (!closedSet.contains(currentMatrixCell)) {
                        addMatrixCellToNeighbours(currentMatrixCell, currentDistance, neighboursMap, predicate);
                        if (numberOfNeighbours != null) {
                            if (getNumberOfNeighbours(neighboursMap) == numberOfNeighbours) {
                                return neighboursMap;
                            }
                        }
                    }
                }
            } else {
                closedSet.add(currentMatrixCell);
            }
            Collection<MatrixCell> neighbours = matrix.getNeighbours(currentMatrixCell).values();
            Set<MatrixCell> neighboursOpenSet = openMap.get(currentDistance + 1);
            if (neighboursOpenSet == null) {
                neighboursOpenSet = new LinkedHashSet<MatrixCell>();
                openMap.put(currentDistance + 1, neighboursOpenSet);
            }
            for (MatrixCell neighbour : neighbours) {
                if (!isMatrixCellBetweenNeighbours(neighbour, neighboursMap)) {
                    neighboursOpenSet.add(neighbour);
                }
            }
        }
        return neighboursMap;
    }

    private boolean isMatrixCellBetweenNeighbours(MatrixCell currentMatrixCell, Map<Integer, Set<MatrixCell>> neighboursMap) {
        for (Set<MatrixCell> matrixCellSet : neighboursMap.values()) {
            if (matrixCellSet.contains(currentMatrixCell)) {
                return true;
            }
        }
        return false;
    }

    private void addMatrixCellToNeighbours(MatrixCell currentMatrixCell, Integer distance, Map<Integer, Set<MatrixCell>> neighboursMap, Predicate predicate) {
        if (predicate.accept(currentMatrixCell)) {
            Set<MatrixCell> neighboursSet = neighboursMap.get(distance);
            if (neighboursSet == null) {
                neighboursSet = new HashSet<MatrixCell>();
                neighboursMap.put(distance, neighboursSet);
            }
            neighboursSet.add(currentMatrixCell);
        }
    }

    private int getNumberOfNeighbours(Map<Integer, Set<MatrixCell>> neighboursMap) {
        int size = 0;
        for (Set<MatrixCell> matrixCellSet : neighboursMap.values()) {
            size += matrixCellSet.size();
        }
        return size;
    }

}
